package com.qzh.baseStruct.Graph;

import lombok.Data;
import lombok.experimental.Accessors;

import java.math.BigDecimal;
import java.util.*;
import java.util.concurrent.atomic.AtomicReference;
import java.util.function.BiConsumer;
import java.util.stream.Collectors;

/**
 * 图结构
 */
public class Graph {
    private final Map<Long,GraphNode>data;
    //记录每id1到每个路径点怎么走，距离是多少
    private final Map<Long,Simplenode>records;
    //空白记录
    private final Simplenode NULL=new Simplenode();

    /**
     * 给定两个id，获取这两个点之间的最短距离，根据权重求值，有多种打印方法
     *
     * @param id1
     * @param id2
     * @param leastPrintMethod
     * @return
     */
    public BigDecimal leastWeightsFromNodes(long id1, long id2, LeastPrintMethod leastPrintMethod) {
        if(!this.data.containsKey(id1))
        {
            throw new RuntimeException("该图不存在输入的节点1");

        }
        if(!this.data.containsKey(id2))
        {
            throw new RuntimeException("该图不存在输入的节点2");

        }
        GraphNode node1 = this.data.get(id1);
        GraphNode node2 = this.data.get(id2);
        BigDecimal weightTotal;
        Map<Long, GraphNode.InnerLine> linked = node1.getLinked();
        //使用迪杰斯特拉算法
        //此map记录由id1点到其他所有点的距离，不记录到自身的距离0，如果非直接连接、禁止通行则设定为最大值。
        Map<Long,BigDecimal> distance = new HashMap<>();

        linked.forEach((aLong, innerLine) -> {
            if(innerLine.getLineType().equals(GraphNode.LineType.banned)||innerLine.getLineType().equals(GraphNode.LineType.onlyEnd)){
            //无法通行的
            distance.put(aLong,BigDecimal.valueOf(Long.MAX_VALUE));
            }
            if(innerLine.getLineType().equals(GraphNode.LineType.normal)||innerLine.getLineType().equals(GraphNode.LineType.onlySrart)){
           //可以通行的
            distance.put(aLong,innerLine.getWeight());
            }
        });
        this.data.keySet().forEach(aLong -> {
            if(!records.containsKey(aLong)){
                records.put(aLong,NULL);
            }
        });
        //经过上述操作后获得的distance为id1有线连接着的所有点的距离，还剩其他所有点。
        this.data.keySet().stream().forEach(aLong -> {
            if(aLong!=id1&&!distance.containsKey(aLong)){//如果id不为id1自身并且不包含在distance则添加进入distance，并且距离设置为无穷
                distance.put(aLong,BigDecimal.valueOf(Long.MAX_VALUE));
            }
        });

        //经过上述操作后的distance包含id1到所有点的距离信息，如果非直连或不可达则距离为无穷。
/*        distance.forEach((aLong, bigDecimal) -> {
            System.out.println("点'"+id1+"'到点'"+aLong+"'的距离为："+bigDecimal.toPlainString());
        });*/
        //记录id1是否已经知道到所有点的距离，初始化都不知道
        Map<Long,Boolean> KnowBooleans =new HashMap<>();
        distance.forEach((aLong, bigDecimal) -> {
            KnowBooleans.put(aLong,false);
        });
        boolean running = true;
        Map<Long,BigDecimal>temp = distance.entrySet().stream().collect(Collectors.toMap(
                Map.Entry::getKey,
                Map.Entry::getValue));
        //
        while(running)
        {
            //这一步的目的是去除已经知道最短路径的key
            KnowBooleans.forEach((aLong, aBoolean) -> {
                if(aBoolean){

                    temp.remove(aLong);
                }
            });
            //找到下一个最短路径的key
          Optional<Map.Entry<Long, BigDecimal>> optional =  temp.entrySet().stream().min(Map.Entry.comparingByValue());
            Long minId =   optional.get().getKey();
            BigDecimal minValue = optional.get().getValue();
            KnowBooleans.replace(minId,true);//如果找到最小值，就是最短路径
            Map<Long, GraphNode.InnerLine>    minLink = this.data.get(minId).getLinked();//id1到这个minId的最短路径确定了，然后再获取minId的最短路径
            //先过滤掉那些无法到达的点
           Set<Map.Entry<Long, GraphNode.InnerLine>> tmp = minLink.entrySet().stream().filter(longInnerLineEntry -> longInnerLineEntry.getValue().getLineType().equals(GraphNode.LineType.normal)|| longInnerLineEntry.getValue().getLineType().equals(GraphNode.LineType.onlySrart)).collect(Collectors.toSet());
            Optional<Map.Entry<Long, GraphNode.InnerLine>> mini =    tmp.stream().min(Comparator.comparing(o -> o.getValue().getWeight()));
             Long a= mini.get().getKey();//这个id是minId能够确定的最短距离的a，需要和distance比较
           List<Long> otherKeys = KnowBooleans.entrySet().stream().filter(longBooleanEntry -> !longBooleanEntry.getValue()).map(i->i.getKey()).collect(Collectors.toList());
            if(a!=id1&&!otherKeys.contains(minId)){
               BigDecimal aDist = distance.get(a);//这是id1到a点的距离
                BigDecimal miniDist = mini.get().getValue().getWeight();//这是minId到a点的距离
                BigDecimal aDistNew = distance.get(minId).add(miniDist);//这是从id1经过minId再到a的距离
                //判断aDist原距离和aDistNew哪一个更小，说明更短，更新distance
                if(aDist.compareTo(aDistNew)>0){
                    distance.replace(a,aDistNew);
                    record(a,minId,miniDist);
                    //record(a,a,miniDist);
                }

            }
            if(!KnowBooleans.containsValue(false))
            {
                running = false;
            }
        }
        if(leastPrintMethod.equals(LeastPrintMethod.onlyNumber))
        {
            distance.forEach((aLong, bigDecimal) -> {
                System.out.println("点'"+id1+"'到点'"+aLong+"'的最短距离为："+bigDecimal.toPlainString());
            });
            Map<Long, LinkedList<Simplenode>> res =   calculateRecord(id1,distance);
            res.size();
        } else if (leastPrintMethod.equals(LeastPrintMethod.withNodes)) {
            distance.forEach((aLong, bigDecimal) -> {
                System.out.println("点'"+id1+"'到点'"+aLong+"'的最短距离为："+bigDecimal.toPlainString());
            });
        }

        return null;
    }
    public Graph(Long id){
        GraphNode firstNode = new GraphNode(id);
        this.data = new HashMap<>();
        this.data.put(id,firstNode);
        this.records = new HashMap<>();
        this.records.put(id,NULL);
    }
    /**
     * 添加节点时，节点本身需要先添加对@id的连接数据，然后再获取@id绑定的节点，添加上连接属性
     */
    public void addLine(long id,long id2,BigDecimal weight, GraphNode.LineType lineType){
        GraphNode node2 = null;
        if (this.data.get(id2) == null) {
             node2 = new GraphNode(id2);
        }
        else
        {
            node2 = this.data.get(id2);

        }
        node2.addLink(id,weight,lineType);
        GraphNode.LineType lineType2 = null;
        if(lineType== GraphNode.LineType.onlySrart){
            lineType2 = GraphNode.LineType.onlyEnd;
        }
        if(lineType== GraphNode.LineType.onlyEnd){
            lineType2 = GraphNode.LineType.onlySrart;
        }
        else
        {
            lineType2 = lineType;

        }        this.data.get(id).addLink(node2.getId(),node2.getWeightFromNodeId(id),lineType2);
        this.data.put(node2.getId(),node2);
    }
    public void printGraph(){
        this.data.forEach(new BiConsumer<Long, GraphNode>() {
            @Override
            public void accept(Long aLong, GraphNode graphNode) {
                AtomicReference<String> keys = new AtomicReference<>("");
                graphNode.getLinked().keySet().forEach(i-> keys.updateAndGet(v -> v + i+","));
                System.out.println("点'"+aLong+"'连接的点是"+keys);
            }
        });
    }

    public void removeNode(long id){
        this.data.remove(id);
    }

    /**
     * 打印最短距离的方法
     */
    public enum LeastPrintMethod{
        /**
         *只有最短距离的数字
         */
        onlyNumber,
        /**
         *带有经过的路径点
         */
        withNodes,
    }

    /**
     * 路径点内部类，用于描述路径
     */
    @Data
    @Accessors(chain = true)
    class Simplenode{
        Long id;
        BigDecimal weight;
    }

    /**
     * 记录id1到每个点id的途径targetId的方法，
     */
   private void record(Long id, Long targetId, BigDecimal weight){
       Simplenode simplenodes = this.records.get(id);
       simplenodes.setId(targetId).setWeight(weight);
    }

    /**
     * 经过上述操作获得的record为记录距离自己最近的一个点，如果为空则就是与id1直连
     */
    private Map<Long,LinkedList<Simplenode>>  calculateRecord(long id1, Map<Long,BigDecimal> distance){
        Map<Long,LinkedList<Simplenode>> newRecords = new HashMap<>();
        LinkedList<Simplenode> NULLLINK = new LinkedList<>();
        //第一次遍历，先把数据为空的找出来附上值
        this.records.entrySet().forEach(longSimplenodeEntry -> {
                newRecords.put(longSimplenodeEntry.getKey(),NULLLINK);
                if(longSimplenodeEntry.getValue()==NULL&&longSimplenodeEntry.getKey().compareTo(id1)!=0)//如果是空白数据。
                {
                    Queue<Simplenode> queue = newRecords.get(longSimplenodeEntry.getKey());
                    queue.add(new Simplenode().setId(longSimplenodeEntry.getKey()).setWeight(distance.get(longSimplenodeEntry.getKey())));
                }
            });
            this.records.entrySet().forEach(longSimplenodeEntry -> {
                if(longSimplenodeEntry.getValue()!=NULL){
                    List<Long>order = new ArrayList<>();
                   Simplenode s = longSimplenodeEntry.getValue();
                   //距离longSimplenodeEntry点最近的一个点是front
                  Long frontId = s.getId();
                  BigDecimal frontBig = s.getWeight();
                    LinkedList<Graph.Simplenode> queue =  newRecords.get(longSimplenodeEntry.getKey());
                        if(queue==NULLLINK)//这些是非空白的，也就是拥有指向前一个点的
                        {
                            
                        }
                }
            });

        return newRecords;
    }
}
